home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / c_toolbx.arc / QSORTI.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-03-30  |  1.3 KB  |  47 lines
  1. /* qsorti.c - preforms a quicksort on an array of integers  */
  2. #include "stdio.h"
  3. #include "cminor.h"
  4.  
  5. int qsort(a,na)
  6.   int    a[]   ;         /* array of integers to be sorted */
  7.   int    na    ;         /* number of elements to be sorted */
  8.   {
  9.      int   i  ,  j   ;        /* indices for loops    */
  10.      int   temp  ;        /* temporary storage for element */
  11.      int   nr ;         /* number elements in right partition  */
  12.      int   part  ;        /* element chosen as partition value */
  13.  
  14.      if( na < 2 )
  15.     return     ;
  16.  
  17.      part = a[na/2]  ;        /* pick middle element for partition */
  18.  
  19.      i = -1 ; j = na ;
  20.      while( 1 ==1 )
  21.     {  /* find first element to move right */
  22.        do {  i = i + 1 ; }    while( a[i] < part ) ;
  23.  
  24.        /* find first element to move left */
  25.        do {  j = j - 1 ; }    while( a[j] > part ) ;
  26.  
  27.        if( i >= j )     /* have the boundries met ? */
  28.           break ;        /* yes - through partitioning */
  29.  
  30.        /* swap i and j elements */
  31.        temp = a[i] ; a[i] = a[j] ; a[j] = temp ;
  32.     }
  33.  
  34.      nr = na - 1 ;
  35.      if( i < (na/2) )        /* now deal with each partition */
  36.     {  qsort( a , i ) ;    /* sort left side */
  37.        qsort( &(a[i]),nr) ; /* sort right side */
  38.     }
  39.      else
  40.     {  qsort( &(a[i]),nr) ; /* sort right side */
  41.        qsort( a , i ) ;    /* sort left side */
  42.     }
  43.   }
  44.  
  45.  
  46.  
  47.